95

­

­

8.2

Complexity and Computing Time of Some Algorithms

Let’s now turn to another problem: How much longer does my calculation take when the

task becomes more difficult? This question is generally called the complexity of a compu­

tational problem.

Polynomial Complexity

In this case, everything is not too computationally intensive. A simple calculation expres­

sion, a so-called polynomial, gives the calculation time as a function of the length.

For example, if an RNA has a length of n nucleotides and is to be folded (i.e., the sec­

ondary structure is calculated), each nucleotide is typically juxtaposed with every other

one along its entire length, and thus sampled for all possible pairs. So this computational

8.2  Complexity and Computing Time of Some Algorithms